public class Partition {
      public static MySingleList.ListNode partition(MySingleList.ListNode pHead,int x) {
          MySingleList.ListNode ah = null;
          MySingleList.ListNode al = null;
          MySingleList.ListNode bh = null;
          MySingleList.ListNode bl = null;

          //遍历整个链表，如果当前节点的值小于x放进a链表
          //如果当前节点的值大于等于x放进b链表
          MySingleList.ListNode curNode = pHead;

          while(curNode != null) {
              MySingleList.ListNode  curN = curNode.next;
              if(curNode.val < x) {
                  //尾插进入a链表
                  //第一次插入，头指针为空
                  if(ah == null) {
                      ah = curNode;
                      al = curNode;
                      curNode.next = null;
                  }
                  else{
                      curNode.next = al.next;
                      al.next = curNode;
                      al = curNode;
                  }


              } else {
                  //尾插进入b链表
                  //第一次插入头指针为空
                  if( bh == null) {
                      bh = curNode;
                      bl = curNode;
                      curNode.next = null;
                  }
                  else{
                      curNode.next = bl.next;
                      bl.next = curNode;
                      bl = curNode;
                  }
              }

              curNode = curN;
          }

          //处理两个链表之中有一个为空的情况
          if(ah == null) {
              return bh;
          }

          if(bh == null) {
              return ah;
          }

          //拼接链表
          al.next = bh;

          //返回链表头节点
          return ah;
      }



    public static void main(String[] args) {

           MySingleList mySingleList = new MySingleList();
           mySingleList.addLast(6);
           mySingleList.addLast(2);
           mySingleList.addLast(8);

           mySingleList.disPlay(mySingleList.head);

           MySingleList.ListNode newHead = partition(mySingleList.head,9);

           mySingleList.disPlay(newHead);

    }
}
